

int Treesize(struct TreeNode* root)
{
    return root == NULL ? 0 : Treesize(root->left) + Treesize(root->right) + 1;
}

void preorder(struct TreeNode* root, int* a, int* pi)
{
    if (root == NULL)
    {
        return;
    }

    a[(*pi)++] = root->val;
    preorder(root->left, a, pi);
    preorder(root->right, a, pi);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {

    *returnSize = Treesize(root);
    int* a = (int*)malloc(*returnSize * sizeof(int));
    int i = 0;
    preorder(root, a, &i);
    return a;
}


int Treesize(struct TreeNode* root)
{
    return root == NULL ? 0 : Treesize(root->left) + Treesize(root->right) + 1;
}

void inorder(struct TreeNode* root, int* a, int* pi)
{
    if (root == NULL)
    {
        return;
    }

    inorder(root->left, a, pi);
    a[(*pi)++] = root->val;
    inorder(root->right, a, pi);

}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = Treesize(root);
    int* a = (int*)malloc(*returnSize * sizeof(int));
    int i = 0;
    inorder(root, a, &i);
    return a;
}


bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if (p == NULL && q == NULL)
    {
        return true;
    }
    if (p == NULL || q == NULL)
    {
        return false;
    }

    if (p->val != q->val)
    {
        return false;
    }

    return isSameTree(p->left, q->left) &&
        isSameTree(p->right, q->right);

}

#include <stdio.h>

struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    char val;
};

struct TreeNode* preorder(char* a, int* pi)
{
    if (a[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }

    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = a[(*pi)++];
    root->left = preorder(a, pi);
    root->right = preorder(a, pi);
    return root;

}

void inorder(struct TreeNode* root)
{
    if (root == NULL)
        return;

    inorder(root->left);
    printf("%c ", root->val);
    inorder(root->right);
}

int main() {
    char a[100];
    scanf("%s", a);
    int i = 0;
    struct TreeNode* root = preorder(a, &i);
    inorder(root);
    return 0;
}

